// 46. 全排列
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

// 示例 1：

// 输入：nums = [1,2,3]
// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
// 思路：排列问题需要一个used数组，标记已经选择的元素
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permute = function(nums) {
    let res=[],ans=[];
    const backtracking=function(used){
        if(ans.length==nums.length){
            res.push([...ans]);
            return;
        }
        for(let i=0;i<nums.length;i++){
            if(used[i]==true) continue;// ans里已经收录的元素，直接跳过
            ans.push(nums[i]);
            used[i]=true;
            backtracking(used);
            ans.pop();
            used[i]=false;
        }
    }
    backtracking([]);
    return res;
};

// 47. 全排列 II（去重）
// 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

// 示例 1：

// 输入：nums = [1,1,2]
// 输出：
// [[1,1,2],
//  [1,2,1],
//  [2,1,1]]
// 思路：先排序，再去重
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permuteUnique = function(nums) {
    let res=[],ans=[];
    nums.sort((a,b)=>a-b);
    const backtracking=function(used){
        if(ans.length==nums.length){
            res.push([...ans]);
            return;
        }
        for(let i=0;i<nums.length;i++){
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
                continue
            }
            if(!used[i]){
                ans.push(nums[i]);
                used[i]=true;
                backtracking(used);
                ans.pop();
                used[i]=false;
            }
            
        }
    }
    backtracking([]);
    return res;
};